package Leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class letterCombinations {
    // 定义一个映射表，将数字与对应的字母组合起来
    String[] table = new String[]{
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
    };

    // 存储所有可能的字母组合结果
    List<String> result = new ArrayList<>();

    // 用于构建单个字母组合的路径
    StringBuilder path = new StringBuilder();

    /**
     * 根据输入的数字字符串，生成所有可能的字母组合
     * @param digits 输入的数字字符串
     * @return 所有可能的字母组合列表
     */
    public List<String> letterCombinations(String digits) {
        // 如果输入字符串为空，则直接返回空的结果列表
        if (digits.isEmpty()){
            return result;
        }
        // 从第一个数字开始回溯生成字母组合
        backtrack(digits, 0);
        return result;
    }

    /**
     * 回溯函数，用于生成字母组合
     * @param digits 输入的数字字符串
     * @param num 当前处理的数字索引
     */
    public void backtrack(String digits, int num){
        // 如果当前处理的数字索引达到了输入字符串的长度，说明已经生成了一个完整的字母组合
        if (num == digits.length()){
            // 将当前的字母组合路径添加到结果列表中
            result.add(path.toString());
            return;
        }
        // 获取当前数字对应的所有可能字母
        String str = table[digits.charAt(num) - '0'];
        // 遍历当前数字对应的所有可能字母
        for (int i = 0; i < str.length(); i++) {
            // 将当前字母添加到路径中
            path.append(str.charAt(i));
            // 递归处理下一个数字
            backtrack(digits, num + 1);
            // 回溯，移除当前路径的最后一个字母，以便尝试下一个可能的字母
            path.deleteCharAt(path.length() - 1);
        }
    }
}
